package com.haoyang.search;

import java.util.Arrays;

public class A02_BinarySearchDemo1 {

    public static void main(String[] args) {
        // 二分查找/折半查找
        // 核心：
        // 每次排除一半的查找范围
        // 需求：定义一个方法利用二分查找，查询某个元素在数组中的索引
        // 数据如下：{7，23，79,81，103，127，131，147}
        long startTime = System.currentTimeMillis();
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
        int targetNumber = 81;
        int resultIndex = binarySearch(arr, targetNumber);
        System.out.println(resultIndex);
        long endTime =  System.currentTimeMillis();
        System.out.println(endTime - startTime);

    }

    /**
     * @param arr:目标数组
     * @parm targetNumber: 目标数字
     */
    public static int binarySearch(int[] arr, int targetNumber) {
        int min = 0;
        int max = arr.length - 1;
//        int mid = (min + max) / 2;
//        for (int i = 0; i < arr.length; i++) {
            // 1.判断数组中间索引的值是否为targetNumber,是则直接返回mid
            // 2.判断arr[mid]与targetNumber的大小关系,
            // 如果arr[mid] > targetNumber: min不变, max = mid - 1(目标值在mid左边)
            // 如果arr[mid] < targetNumber: max不变, min = mid + 1(目标值在mid右边)
            // 一直递归,直到arr[mid] = targetNumber(递归结束条件)
//            if (arr[mid] == targetNumber) {
//                return mid;
//            }
//            if (arr[min] == targetNumber) {
//                return min;
//            }
//            if (arr[max] == targetNumber) {
//                return max;
//            }
//            if (arr[mid] > targetNumber) {
//                max = mid - 1;
//                int[] newArr = Arrays.copyOfRange(arr, min, max);
//                binarySearch(newArr, targetNumber);
//            } else {
//                min = mid + 1;
//                int[] newArr = Arrays.copyOfRange(arr, min, max);
//                binarySearch(newArr, targetNumber);
//            }
//        }
//        return -1;
        while (true) {
            if (min > max) {
                return -1;
            }
            int mid = (min + max) / 2;
            if (arr[mid] > targetNumber) {
                max = mid - 1;
            } else if (arr[mid] < targetNumber) {
                min = mid + 1;
            } else {
                return mid;
            }

        }
    }
}
